public class QuickSort {

    public static void quickSort(int[] arr){
        Sort(arr,0,arr.length-1);
    }
    public static void Sort(int[] arr,int low,int high){
        if (low<high){
            int flag=partition(arr,low,high);
            Sort(arr,low,flag-1);
            Sort(arr,flag+1,high);
        }
    }

    private static int partition(int[] arr, int low, int high) {//获得分界值的下标
        int temp=arr[low];//第一次递归时先取第一个数做基准值
        while (low<high){
            while (low<high&&arr[high]>=temp){//右边的数字比temp大则high--
                high--;
            }
            arr[low]=arr[high];//将high位置挖一坑，表示待填，并将high位的值赋给low位
            while (low<high&&arr[low]<=temp){
                low++;
            }
            arr[high]=arr[low];//将low位挖一坑，表示待填，并将low位的值赋给high位
        }
        arr[low]=temp;
        return low;
    }
}
